package 剑指Offer.medium;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class 队列的最大值 {
    class MaxQueue {

        //普通队列
        private Queue<Integer> queue = new LinkedList<>();
        //单调递减双端队列
        private Deque<Integer> deque = new LinkedList<>();

        public MaxQueue() {

        }

        public int max_value() {
            if (queue.isEmpty()) return -1;
            return deque.peekFirst();
        }

        public void push_back(int value) {
            queue.add(value);
            while (!deque.isEmpty() && deque.peekLast() < value) {
                deque.pollLast();
            }
            deque.addLast(value);
        }

        public int pop_front() {
            if (queue.isEmpty()) return -1;
            Integer pop = queue.poll();
            if (pop == deque.peekFirst()) {
                deque.pollFirst();
            }
            return pop;
        }
    }
}
